/*
 * SolvePuzzle.java
 *
 * Created on 2007年10月10日, 下午8:45
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package cn.tearcry.jsudoku;
import java.util.*;
/**
 *
 * @author 马建乐
 */
public class SolvePuzzle {
    /** 无解标志 */
    private int outsign=0;
    /** 初始置入的题目 */
    private int[][] number;
     /** 记录解题步骤 */
    private int[][] answer=new int[9][9];
    /** 确定的数字的位置标志 */
    private int[][] check=new int[9][9];        
    /** 行，列的集合 */
    private int[][] check1=new int[18][10];        
    /** 九宫格集合 */
    private int[][][] check2=new int[3][3][10];    
    /** 用于递归时保存数据 */
    private int[] f1=new int[100];            
    /** 保存已猜测过的数字 */
    private int[] sign=new int[100];            
    /** 结束猜测的数目 */
    private int end;   
    /** 栈 */
    private int[] stack=new int[100];
    /** 栈顶位置 */
    private int top=1;
    
    private ArrayList stepList=new ArrayList ();
    /**
     * 初始化
     */
    private void init() {        
        for (int i=0; i<9; i++) {
           for (int j=0; j<9; j++)
            check[i][j]=0; 
        }

        for (int i=0; i<18; i++) {
          for (int j=0; j<10; j++)
            check1[i][j]=0;
        }

         for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++)
                for (int k=0; k<10; k++)
                    check2[i][j][k]=0;
         }
          
        for (int i=0; i<100; i++)
             sign[i]=0;          
      
        end=0;  
}
    public SolvePuzzle(int[][] puzzleArray) {
       number=new int[9][9];
        for(int i=0;i<number.length;i++)
            for(int j=0;j<number[i].length;j++)
                number[i][j]=puzzleArray[i][j];
       this.solve();
    }

private void input() {
   
    int num=0,
        know=0;
    
    for (int i=0; i<9; i++) {
        for (int j=0; j<9; j++) {
            num=number[i][j]; 
            if (number[i][j] == 0) {
                check[i][j]=0;
                if (outsign == 0) outsign=i*8+j;
            }
            else {
                know++;
                check[i][j]=1;
                check1[i][num]=1;
                check1[j+9][num]=1;
                check2[i/3][j/3][num]=1;
                check1[i][0]++;
                check1[j+9][0]++;
                check2[i/3][j/3][0]++;
            }
        }
    }
    end=81-know;
  
}


private int findMinAll()
{
    int n, i, j,t,mark;
    int min, cord=81;
    min=10;

    for (n=0; n<81; n++)
    {   
		mark=0;
        i=n/9;
        j=n%9;
        if (check[i][j] == 1) continue;
        if (sign[n] == 1) continue;
		for(t=1;t<=9;t++)
		{
			if(check1[i][t]==0)
			{
				if((check1[j+9][t]==0)&&(check2[i/3][j/3][t]==0))
					mark++;
			}
		}
	
		if(mark<min)
		{
			min=mark;
			cord=n;
		}
	
    }
	
    return cord;
}

private boolean find(int n, int m)
{//递归搜索
    int i, j;
    if (m<end)
    {
        for (int k=1; k<=9; k++)
        {
            i=n/9;
            j=n%9;
            if (check1[i][k] == 1) continue;
            if (check1[j+9][k] == 1) continue;
            if (check2[i/3][j/3][k] == 1) continue;
            check1[i][k]=1;
            check1[j+9][k]=1;
            check2[i/3][j/3][k]=1;
            f1[n]=k;
            sign[n]=1;
			stack[top]=n;
			top++;
            int min=findMinAll();
            if (find(min, m+1)) return true;
            sign[n]=0;
            check1[i][k]=0;
            check1[j+9][k]=0;
            check2[i/3][j/3][k]=0;
			top--;
        }
        return false;
    }
    else
    {
        int bb=-1;
        for (i=0; i<9; i++)
            for (j=0; j<9; j++)
            {
                bb++;
                if ( check[i][j] == 0) answer[i][j]=f1[bb];
                else answer[i][j]=number[i][j];
            }
            return true;
    }
}



    
    public  ArrayList getStepList() {
        for(int i=1;i<top;i++)             
            stepList.add(Integer.valueOf(stack[i]));
        return stepList;
    }
    public int blankNumber() {
        return top;
    }
    
    public int[][] getAnswer() {
        return answer;
    }

    private  void solve() {
            
            init();
            input();
            int m=findMinAll();
            find(m,0);        
        /** 输出
        System.out.println();
	for(int j=1;j<top;j++)
	System.out.printf(stack[j]+" ");
	System.out.println();
         */
    }


    
    
    public static void main(String[] args ) {
        
        int[][] array= { { 0, 7, 0, 0, 0, 2, 5, 1, 0 },
            { 5, 0, 0, 0, 8, 0, 0, 3, 0 }, { 0, 3, 0, 0, 0, 5, 0, 9, 0 },
            { 0, 5, 0, 0, 6, 3, 4, 0, 0 }, { 9, 0, 0, 0, 7, 0, 0, 0, 3 },
            { 0, 0, 1, 0, 0, 4, 0, 2, 0 }, { 0, 6, 0, 8, 0, 0, 0, 7, 0 },
            { 0, 2, 0, 0, 5, 0, 0, 0, 8 }, { 0, 9, 3, 7, 0, 0, 0, 6, 0 } };
        SolvePuzzle puzzle=new SolvePuzzle(array);
        puzzle.solve();
        Iterator iter=puzzle.getStepList().iterator();
        System.out.println();
        while(iter.hasNext())
            System.out.print(((Integer)iter.next()).intValue()+" ");
    }
    
    
    
}
